用 python 打算法竞赛

还没看完

学习字典 dict（字典 dict 还没有写完！！！）
上面的文章还没看完！！！从3.3开始看I（还有自带函数，如 sorted 等等）
补一下基本数据结构的使用
复习 numpy
学习 collection

/ 是浮点数的除法，// 是整除，% 是取余

头文件模板：

import sys
import os
import time
from functools import reduce
from math import *

if __name__ == "__main__" :
	pass

输入&输出

整数的输入

n, m = map(int, input().split()) # 接收两个整数，以空格隔开
arr = list(map(int, input().split())) # 接收 n 个整数的数组，以空格隔开

不定长输入

直接读入一行数据： sys.stdin.readline()

一次性读入所有数据： sys.stdin.readlines()

要注意的是，readlines() 获取到的字符串列表通常会包含一个换行符\n，在进行处理的时候，根据需要使用 strip() 或 rstrip() 将最右边的换行符去掉。具体参考string.strip().

如果要从文件中读入：

with open("filename.txt", "r") as f:
    p = f.readlines()

数组输出

要求输出数字以空格分开的简易写法：

result = [1, 2, 3, 4, 5]
print(*result)

如果每行输出一个数字，将 print 的 seq 参数改为 \n 即可：

print(*result, sep = "\n")

参考：print

小数输出

方法1：使用格式字符串

pi = 3.1415926

# 格式化小数点后两位
formatted_pi = f"The value of pi is {pi:.2f}"
print(formatted_pi)

格式字符串的更多用法，参考格式字符串

方法2：使用 round 函数

num = 3.1415926

# 四舍五入到小数点后四位
rounded_num = round(num, 4)
print(rounded_num)  # 输出：3.1416

常用技巧（加速/简化）

快速初始化

对于某些特例，比如并查集，需要初始化元素和下标相等的列表，直接使用 list() 方法将 range 对象转成列表更快。

arr = list(range(100))
# arr = [0, 1, 2, 3, 4,..., 98, 99]

使用推导式生成列表和字典

使用列表推导式（生成式）生成列表，要比使用 for 循环更快，字典也是一样。

p = [i for i in range(100)]
d = {i: j for i, j in enumerate(range(100))}

善用元组、集合与字典

Python的集合与字典使用哈希表的方式存储，从而可以做到时间复杂度为 $O (1)$ 的常数级读取。

集合还可以用来去重，以及自带一些数学上的集合操作. 更多请看：集合 set

nums = {1, 2, 3, 4, 5}
if 2 in nums:

元组是唯一可以被哈希化的容器：也就是说，多元组可以放进集合、字典，从而在保证去重的同时，还可用来常数级读取判断某个多元组存不存在

全局变量

Python 中的全局变量需要在函数中用 global 命令声明后才能进行修改，例子如下:

x = 0
def foo():
    x += 10
def bar():
    global x
    x += 10
def main():
    foo()
    bar()

调用 foo() 会抛出 UnboundLocalError: local variable 'x' referenced before assignment

重定向输入输出

import sys
sys.stdin = open(r'hack.txt', 'r')   # r表示raw string
sys.stdout = open(r'hack.out', 'w')

reduce & map

非常常用的两个函数

调试

调试 `debug`

LOCAL = not __debug__ # True if compile option '-O'

if LOCAL:  # 在本地调试，而不是 OJ 评测
    print("Hello")

assert

在抛出 AssertionError 时可以指定报错信息

a, b = 1, 2
assert a == b, f'{a} != {b}'

终端会抛出 AssertionError: 1 != 2

随机数生成

import sys
from random import *

# seed(12345)
sys.stdout = open(r'hack.txt', 'w')

n = int(1e3)
print(n)
for i in range(n):
    a = randint(-1e9, 1e9)
    b = randint(-1e9, 1e9)
    print(a, b)

代码计时

import time

if __name__ == '__main__':
    T1 = time.time()
    main()
    T2 = time.time()
    print("Runtime: %.3f s." % (T2 - T1), file=sys.stderr)

print() 的 kwg 中指定 file=sys.stderr 使得运行时间在终端输出。这样当重定向输入输出时，该语句不受影响。